#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 解法与三数之和类似，双重循环，双指针
 *   n数之和类似的题暴力解法时间复杂度（n ^ n）
 *   使用双指针解法后时间复杂度可降低一个数量级（n ^ n-1）
 * 
 * 每个符合条件的元组 a, b, c, d 四个数
 */
vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    // i 从索引 0 开始，且取不到后两位，已经留给 c d 了
    for (int i {}, len1 = nums.size(); i < len1 - 2; i++) {
        // 第一个数已经大于 target，那么后面数都大于 target，没有符合条件的元组了
        // 此时上面判断已经不再成立，因为target可能为负数
        if (nums[i] > target && nums[i] > 0) {
            return result;
        }
        // 去重 a
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        // j 从索引 i + 1 开始，且取不到后两位，已经留给 c d 了
        for (int j { i + 1 }, len2 = nums.size(); j < len2 - 2; j++) {
            // 同理
            if (nums[i] + nums[j] > target && nums[i] + nums[j] > 0) {
                // 这里不能直接 return 结果，应该跳出这层循环
                // 直接返回结果将漏掉其它的情况
                break;
            }
            // 去重 b
            if (j > i + 1 && nums[j] == nums[j - 1])  {
                continue;
            }

            // 定义双指针
            // left 从索引 j + 1 开始
            // right 从索引 len - 1 开始
            int left { j + 1 }, right { len2 - 1 };
            while (left < right) {
                // 这里需要使用 long int 不然会溢出
                // int 转 long
                long sum { (long)nums[i] + nums[j] + nums[left] + nums[right] };
                if (sum > target) {
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    result.push_back({ nums[i], nums[j], nums[left], nums[right] });
                    // 去重 c
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    // 去重 d
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    // 双指针收缩
                    left++;
                    right--;
                }
            }
        }
    }

    return result;
}

void printVector(vector<vector<int>>& nums) {
    for (int i = 0, len1 = nums.size(); i < len1; i++) {
        string str { "[" };
        for (int j = 0, len2 = nums[i].size(); j < len2; j++) {
            str += (to_string(nums[i][j]) + (j < len2 - 1 ? ", " : ""));
        }
        str += "]";
        cout << str << "\n";
    }
}

int main() {
    vector<int> nums { 0,0,0,1000000000,1000000000,1000000000,1000000000 };
    vector<vector<int>> result { fourSum(nums, 1000000000) };
    printVector(result);
    
    return 0;
}